package Top_Interview_Questions.Greedy;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/20 16:29
 * <p>
 * 这个地方动态规划讲的不错。
 *
 * https://leetcode-cn.com/problems/jump-game/solution
 * /tiao-yue-you-xi-by-leetcode/
 */

enum Index {
    GOOD, BAD, UNKNOWN
}
public class _0055 {

    public static void main(String[] args) {
        _0055 test = new _0055();
        int[] numTrue = {2,3,1,1,4};  //这个是全是好位置的数组
        int[] numFalse = {3,2,1,0,4}; //这个是全是坏位置的数组
        int[] num = {2, 4, 2, 1, 0, 2, 0};  //这个是有好位置也有坏位置的数组
        int[] numGreedy = {9, 4, 2, 1, 0, 2, 0};  //贪心测试专用

        test.canJump4(numGreedy);
    }

/*---------------------------------------贪心-----------------------------------------*/

    public boolean canJump4(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }

/*-----------------------------------------------------------------------------------*/


/*---------------------------------自底向上的动态规划-----------------------------------*/

    public boolean canJump3(int[] nums) {
        Index[] memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;

        for (int i = nums.length - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], nums.length - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (memo[j] == Index.GOOD) {
                    memo[i] = Index.GOOD;
                    break;
                }
            }
        }

        return memo[0] == Index.GOOD;
    }

/*-----------------------------------------------------------------------------------*/

/*---------------------------------自顶向下的动态规划-----------------------------------*/
    Index[] memo;

    public boolean canJumpFromPosition(int position, int[] nums) {
        if (memo[position] != Index.UNKNOWN) {
            return memo[position] == Index.GOOD ? true : false;
        }
        //总的来说就是先跳一步，不行的话，再跳两步。只要没超过它最大可以跳到的地方，就一直试下去
        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                memo[position] = Index.GOOD;
                return true;
            }
        }

        memo[position] = Index.BAD;
        return false;
    }

    public boolean canJump2(int[] nums) {
        memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;
        return canJumpFromPosition(0, nums);
    }

/*--------------------------------------------------------------------------------*/


/*------------------------------------回溯法--------------------------------------*/

    /**
     * 时间复杂度最高的回溯法
     *
     * 1.nextPosition <= furthestJump;这个限制条件只约束输出为false的情况,debug就能比较清楚的
     * 看到整个回溯的过程
     */
    public boolean canJumpFromPosition1(int position, int[] nums) {
        if (position == nums.length - 1) {
            return true;
        }

        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        //1.
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition1(nextPosition, nums)) {
                return true;
            }
        }

        return false;
    }

    public boolean canJump1(int[] nums) {
        return canJumpFromPosition1(0, nums);
    }

    /*--------------------------------------------------------------------------------*/


}
